home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / xdme_1.84_src.lha / XDME / Lib / src / SLL.c < prev   
Encoding:
C/C++ Source or Header  |  1994-11-25  |  6.9 KB  |  241 lines
  1. /******************************************************************************
  2.  
  3.     MODULE
  4.     SLL.c
  5.  
  6.     DESCRIPTION
  7.     Type SLL - Single Linked List
  8.  
  9.     This module is used to simplify work with some Intuition
  10.     structures like Windows, Menus, MenuItems, Gadgets ...
  11.  
  12.     HISTORY
  13.     30-10-94 b_noll created
  14.     14-11-94 b_noll cleaned up using SList/SNode
  15.     $Log: SLL.c $
  16.  
  17. ******************************************************************************/
  18.  
  19. /**************************************
  20.           Includes
  21. **************************************/
  22.  
  23. #ifndef   SLL_H
  24. #include <SLL.h>
  25. #endif /* SLL_H */
  26.  
  27. /**************************************
  28.       Internal Defines & Structures
  29. **************************************/
  30.  
  31. #define Prototype extern
  32. #undef    SLL_GetHead
  33. #undef    SLL_GetTail
  34. #undef    SLL_GetSucc
  35. #undef    SLL_GetPred
  36. #undef    SLL_Init
  37.  
  38. /**************************************
  39.          Implementation
  40. **************************************/
  41.  
  42. Prototype void SLL_Init (struct SList *l);
  43. void SLL_Init (struct SList *l) {
  44.     l->Head = NULL;
  45. } /* SLL_Init */
  46. #define SLL_Init(l) (l)->Head=NULL
  47.  
  48. Prototype struct SNode *SLL_GetHead (struct SList *l);
  49. struct SNode *SLL_GetHead (struct SList *l) {
  50.     return l->Head;
  51. } /* SLL_GetHead */
  52. #define SLL_GetHead(l) ((l)->Head)
  53.  
  54. Prototype struct SNode *SLL_GetSucc (struct SList *l, struct SNode *n);
  55. struct SNode *SLL_GetSucc (struct SList *l, struct SNode *n) {
  56.     return n->Succ;
  57. } /* SLL_GetSucc */
  58. #define SLL_GetSucc(l,n) ((n)->Succ)
  59.  
  60. Prototype struct SNode *SLL_GetPred (struct SList *l, struct SNode *n);
  61. struct SNode *SLL_GetPred (struct SList *l, struct SNode *n) {
  62.     struct SNode *m, *p;
  63.     if (!(p = SLL_GetHead(l)) || (p == n))
  64.     return NULL;
  65.     while ((m = SLL_GetSucc(l,p)) && (m != n))
  66.     p = m;
  67.     return (m == n)? p: NULL;
  68. } /* SLL_GetPred */
  69.  
  70. Prototype struct SNode *SLL_GetTail (struct SList *l);
  71. struct SNode *SLL_GetTail (struct SList *l) {
  72.     return SLL_GetPred(l,NULL);
  73. } /* SLL_GetTail */
  74. #define SLL_GetTail(l) SLL_GetPred(l,NULL)
  75.  
  76. Prototype struct SNode * SLL_NumToNode (struct SList *l, int i);
  77. struct SNode * SLL_NumToNode (struct SList *l, int i) {
  78.     struct SNode *n;
  79.     for (n = SLL_GetHead(l); n && i--; n = SLL_GetSucc(l,n));
  80.     return n;
  81. } /* SLL_NumToNode */
  82.  
  83. Prototype int SLL_NodeToNum (struct SList *l, struct SNode *n);
  84. int SLL_NodeToNum (struct SList *l, struct SNode *n) {
  85.     struct SNode *m;
  86.     int       i;
  87.     for (i = 0, m = SLL_GetHead(l); m && (m != n); ++i, m = SLL_GetSucc(l,m));
  88.     return (m == n)? i: NULL;
  89. } /* SLL_NodeToNum */
  90.  
  91. Prototype int SLL_Length (struct SList *l);
  92. int SLL_Length (struct SList *l) {
  93.     return SLL_NodeToNum(l, NULL);
  94. } /* SLL_Length */
  95.  
  96. Prototype struct SNode *SLL_RemHead (struct SList *l);
  97. struct SNode *SLL_RemHead (struct SList *l) {
  98.     struct SNode *n;
  99.     if ((n = SLL_GetHead(l))) {
  100.     SLL_Remove(l,n);
  101.     } /* if */
  102.     return n;
  103. } /* SLL_RemHead */
  104.  
  105. Prototype struct SNode *SLL_RemTail (struct SList *l);
  106. struct SNode *SLL_RemTail (struct SList *l) {
  107.     struct SNode *n;
  108.     if ((n = SLL_GetTail(l))) {
  109.     SLL_Remove(l,n);
  110.     } /* if */
  111.     return n;
  112. } /* SLL_RemTail */
  113.  
  114. /* ---- SLL Internal - append an entry to another */
  115.  
  116. static void _SLL__AddAfter (struct SNode *new, struct SNode *pos) {
  117.     new->Succ = pos->Succ;
  118.     pos->Succ = new;
  119. } /* SLL_AddAfter */
  120.  
  121. /* ---- Append an entry at the end of a SLL */
  122.  
  123. Prototype void SLL_AddTail (struct SList *l, struct SNode *n);
  124. void SLL_AddTail (struct SList *l, struct SNode *n) {
  125.     struct SNode *p;
  126.     if ((p = SLL_GetTail(l)))
  127.     _SLL__AddAfter(  n,p);
  128.     else
  129.     SLL_AddHead(l,n);
  130. } /* SLL_AddTail */
  131.  
  132. /* ---- Add a new entry at the head of a SLL */
  133.  
  134. Prototype void SLL_AddHead (struct SList *l, struct SNode *n);
  135. void SLL_AddHead (struct SList *l, struct SNode *n) {
  136.     _SLL__AddAfter(  n,(struct SNode *)l);
  137. } /* SLL_AddHead */
  138.  
  139. /* ---- Add a new entry into a SLL in front of a given entry */
  140.  
  141.  
  142. Prototype void SLL_AddInfront (struct SList *l, struct SNode *n, struct SNode *pos);
  143. void SLL_AddInfront (struct SList *l, struct SNode *n, struct SNode *pos) {
  144.     struct SNode *p;
  145.     if ((p = SLL_GetPred(l,pos)))
  146.     _SLL__AddAfter(  n,p);
  147.     else
  148.     SLL_AddHead(l,n);
  149. } /* SLL_AddInfront */
  150.  
  151. /* ---- Add a new entry into a SLL behind a given entry */
  152.  
  153. Prototype void SLL_AddBehind (struct SList *l, struct SNode *n, struct SNode *pos);
  154. void SLL_AddBehind (struct SList *l, struct SNode *n, struct SNode *pos) {
  155.     _SLL__AddAfter(  n,pos);
  156. } /* SLL_AddBehind */
  157.  
  158. /* ---- Find an entry in a SLL */
  159.  
  160. Prototype struct SNode *SLL_Find (struct SList *l, int (*find)(void *, APTR, int), APTR userdata);
  161. struct SNode *SLL_Find (struct SList *l, int (*find)(void *, APTR, int), APTR userdata) {
  162.     struct SNode *n;
  163.     int       i = 0;
  164.     for  (n = SLL_GetHead(l); n; n = SLL_GetSucc(l,n))
  165.     if (!(*find) (n, userdata, i++))
  166.         return n;
  167.     return NULL;
  168. } /* SLL_Find */
  169.  
  170. /* ---- Step through all entries of a SLL (may be used to delete) */
  171.  
  172. Prototype void SLL_Scan (struct SList *l, void (*scan) (void *, APTR, int), APTR userdata);
  173. void SLL_Scan (struct SList *l, void (*scan) (void *, APTR, int), APTR userdata) {
  174.     struct SNode *n, *nn;
  175.     int       i = 0;
  176.     for (nn = SLL_GetHead(l); (n = nn); nn = SLL_GetSucc(l,nn))
  177.     (*scan) (n, userdata, i++);
  178. } /* SLL_Scan */
  179.  
  180. /* ---- Remove an entry from a SLL */
  181.  
  182. BOOL SLL_Remove (struct SList *l, struct SNode *n) {
  183.     struct SNode *m, *p;
  184.     for (p = (void *)l; m = SLL_GetSucc(l,p); p = m)
  185.     if (m == n) {
  186.         p->Succ = n->Succ;
  187.         n->Succ = NULL;
  188.         return TRUE;
  189.     } /* if */
  190.     return FALSE;
  191. } /* SLL_Remove */
  192.  
  193.  
  194.  
  195.  
  196.  
  197. /* cleaned up up to here ... at 14-11-94 */
  198.  
  199.  
  200.  
  201. #if 0
  202.  
  203. /* ---- Create a node, if it does not yet exist in a SLL */
  204.  
  205. Prototype void *SLL_Find_or_Append (void *sll, int (*find)(void*, ULONG), void *(Create)(ULONG), ULONG userdata);
  206. void *SLL_Find_or_Append (SLL *sll, int (*find)(void*, ULONG), void *(Create)(ULONG), ULONG userdata) {
  207.     void *inter;
  208.     inter = SLL_Find (sll, find, userdata);
  209.     if (!inter) {
  210.     inter = (*Create) (userdata);
  211.     if (inter)
  212.         SLL_AddTail (sll, inter);
  213.     } /* if */
  214.     return inter;
  215. } /* SLL_Find_or_Append */
  216.  
  217. /* ---- Delete an entry in a SLL */
  218.  
  219. Prototype void SLL_Delete (void *sll, void *remove, void (*delete)(void *, ULONG), ULONG userdata);
  220. void SLL_Delete (SLL *sll, void *remove, void (*delete)(void *, ULONG), ULONG userdata) {
  221.     SLL_Remove (sll, remove);
  222.     (*delete) (remove, userdata);
  223. } /* SLL_Delete */
  224.  
  225. Prototype BOOL SLL_Find_and_Delete (void *sll, int (*find)(void *, ULONG), void (*delete)(void *, ULONG), ULONG userdata);
  226. BOOL SLL_Find_and_Delete (SLL *sll, int (*find)(void *, ULONG), void (*delete)(void *, ULONG), ULONG userdata) {
  227.     void *inter;
  228.     if ((inter = SLL_Find (sll, find, userdata)) {
  229.     SLL_Remove (sll, inter);
  230.     (*delete) (inter, userdata);
  231.     return TRUE;
  232.     } /* if */
  233.     return FALSE;
  234. } /* SLL_Find_and_Delete */
  235.  
  236. #endif
  237.  
  238. /******************************************************************************
  239. *****  END SLL.c
  240. ******************************************************************************/
  241.